
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1628. -- [Usaco2007 Demo]City skyline -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1628: [Usaco2007 Demo]City skyline</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>115&nbsp;&nbsp;<span class=green>Solved: </span>95<br>[<a href='submitpage.php?id=1628'>Submit</a>][<a href='problemstatus.php?id=1628'>Status</a>][<a href='bbs.php?id=1628'>Discuss</a>]</center><h2>Description</h2><div class=content>The best part of the day for Farmer John's cows is when the sun
sets. They can see the skyline of the distant city. Bessie wonders
how many buildings the city has. Write a program that assists the
cows in calculating the minimum number of buildings in the city,
given a profile of its skyline.

The city in profile is quite dull architecturally, featuring only
box-shaped buildings. The skyline of a city on the horizon is
somewhere between 1 and W units wide (1 <= W <= 1,000,000) and
described using N (1 <= N <= 50,000) successive x and y coordinates
(1 <= x <= W, 0 <= y <= 500,000), defining at what point the skyline
changes to a certain height.

An example skyline could be:
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

and would be encoded as (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2),
(17,3), (20,2), (22,1).

给我们一个由一些矩形构造出来的图，我们需要找到最少矩形的块数来覆盖它

但是这个输入比较奇怪,针对上图,解释如下:
1.1代表在第一列,有高度为1的矩形,矩形由"X"组成.这个矩形有多宽呢,这里并没有告诉你
2.2代表在第二列,有高度为2的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即2-1
5.1代表在第五列,有高度为1的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即5-2





This skyline requires a minimum of 6 buildings to form; below is
one possible set of six buildings whose could create the skyline
above:

..........................    ..........................
.....22.........333.......    .....XX.........XXX.......
.111.22.......XX333XX.....    .XXX.XX.......5555555.....
X111X22XXX....XX333XXXXXXX    4444444444....5555555XXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

</div><h2>Input</h2><div class=content>* Line 1: Two space separated integers: N and W

* Lines 2..N+1: Two space separated integers, the x and y coordinate
        of a point where the skyline changes. The x coordinates are
        presented in strictly increasing order, and the first x
        coordinate will always be 1.

</div><h2>Output</h2><div class=content>* Line 1: The minimum number of buildings to create the described
        skyline.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>10 26<br />
1 1<br />
2 2<br />
5 1<br />
6 3<br />
8 1<br />
11 0<br />
15 2<br />
17 3<br />
20 2<br />
22 1<br />
<br />
INPUT DETAILS:<br />
<br />
The case mentioned above<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>6<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver
'>Silver<br />
</a></p></div><center>[<a href='submitpage.php?id=1628'>Submit</a>][<a href='problemstatus.php?id=1628'>Status</a>][<a href='bbs.php?id=1628'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
